【考试总结】 Test-2019.4.3 HNOI2019模拟 | Qiuly's blog!

【考试总结】 Test-2019.4.3 HNOI2019模拟

Posted on | In | Comments:

三道题目，一眼出算法。

第一道题目显然是后缀自动机，
第二道题目显然是莫比乌斯反演加上杜教筛。
第三道题目显然是网络流。

然而考场上都没做出来……自闭了。

真的，现在已经是傍晚了，大后天就是毒瘤的省选了……小学中现在正在举办运动会，班级群中一群人在那里一个劲的喊加油，但是，班上有人给我加油吗？除了几个好朋友之外……

题目压缩包戳我!!!~\(≧▽≦)/~(有时链接可能会崩，如果崩了的话请稍后尝试QwQ)

T1

期望得分：40分
实际得分：40分
正解：后缀自动机(SAM)+FFT
窝的解法：哈希

题解

嗯后缀自动机是会的但是感觉不好做。

于是弄了个哈希上去骗分，暴力枚举字串然后玄学哈希即可。

不会正解。。。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=666;
const int inf=1e9+9;
const int MOD=100000007;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int k,m,cnt,res[N*N],ans;
char s[N],c[N];
map<int,int> hash;

void dfs(int step,int sum) {
    if(step==k+1&&sum==m) {++ans;return;}
    if(step==k+1) return;
    if(sum>m) return;
    for(int i=1;i<=cnt;++i)
        dfs(step+1,sum+res[i]);
    return;
}

int main() {
    freopen("tele.in","r",stdin);
    freopen("tele.out","w",stdout);
    IN(k),IN(m);
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;++i) 
        for(int j=i;j<=n;++j) {
            int tot=0;
            for(int k=i;k<=j;++k) tot=(1ll*tot*27%MOD+s[k]-'a'+1)%MOD;
            /*大力玄学哈希+map判重*/
            hash[tot]++;
        }
    for(int i=1;i<=n;++i) 
        for(int j=i;j<=n;++j) {
            int tot=0;
            for(int k=i;k<=j;++k) tot=(1ll*tot*27%MOD+s[k]-'a'+1)%MOD;
            res[++cnt]=hash[tot];
        }
    dfs(1,0);
    /*灵机一动这样写，那么k打于2的时候如果数据小可以多拿一些分*/
    /*实验证明这样布星*/
    printf("%d\n",ans);
    return 0;
}

T2

期望得分：60分
实际得分：40分
正解：莫比乌斯反演+杜教筛
窝的解法：莫比乌斯反演

题解

考场上忘记了杜教筛，于是GG。

本来有六十分的……脑抽的窝，预处理 $\sum_{i=1}^{T}\lfloor\frac{T}{i}\rfloor$ 居然用 $O(n\sqrt{n})$ 来解决……实际上改两个字符就变成 $O(n)$ 的复杂度了，就有 $60$ 分了……

嗯然后筛 $\mu$ 的时候可以搞个杜教筛加速，这样子的话 $\mu$ 函数的前缀和就可以 $O(n^{\frac{2}{3}})$ 筛出。不过估计是标程质量不行，题目范围只有 $10^9$ ……杜教筛可以解决 $O(10^{11})$ 左右的问题……吧?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <map>
#include <cstdio>
#include <bitset>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=4e6;
const int inf=1e9+9;
const int MOD=1000000007;

bitset<N+7> vis;
int n,mui[N+7],prime[N],cnt;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

inline void pre() {
    mui[1]=1;
    for(int i=2;i<N;++i) {
        if(!vis[i]) prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<N;++j) {
            vis[i*prime[j]]=1;
            if(!(i%prime[j])) {mui[i*prime[j]]=0;break;}
            else mui[i*prime[j]]=-mui[i];
        }
    }for(int i=1;i<N;++i) mui[i]+=mui[i-1];
    return;
}
ll S(int MX) {
    ll sum=0;
    for(int l=1,r;l<=MX;l=r+1) {
        r=MX/(MX/l);
        sum=(sum+1ll*(r-l+1)*(MX/l)%MOD)%MOD;
    }return sum;
}

map<int,int> MU;
int Sum(int x) {/*杜教筛*/
    if(x<N) return mui[x];
    else if(MU.count(x)) return MU[x];
    else if(!x) return 0;
    else {
        int s=1;
        for(int l=2,r;l<=x;l=r+1) {
            r=x/(x/l);
            s-=(r-l+1)*Sum(x/l);
        }return MU[x]=s;
    }
}

int main() {
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    scanf("%d",&n);
    pre();
    ll res=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ll num=S(n/l);
        res=(res+1ll*(Sum(r)-Sum(l-1))*num*num%MOD+MOD)%MOD;
    }		
    printf("%lld\n",(res+MOD)%MOD);
    return 0;
}

嗯实际这题窝觉得是一道莫反板子题，但是没做出来，看来杜教筛还是不会……

T3

期望得分：50分
实际得分：0分
正解：最小割
窝的解法：最小割+爆搜

题解

看完题目后，窝决定第一个看这道题。

哇，一眼网络流题目欸！

咦这题好像小$M$的作物欸，但是第二个操作又不对劲了……(实际上第二个操作就是文理分科那题，但是窝没做那题)。

嗯，需要花费的什么费用……费用流？！然后手画了一下图……自己模拟一下发现根本不好模拟，想着费用流板子也就 $10$ 分钟的事，于是打了个费用流照着窝之前的想法建一下边，跑一下后发现错了……

然后苦苦思索……转眼间 $30$ 分钟过去了。发现时间过得比较快，于是决定先将暴力 $30$ 打好再想……嗯爆搜一下救过了样例(不过窝的爆搜又打错了以至于窝没拿到分？！)

嗯这个时候感觉前 $30$ 分稳了，于是观察部分分，发现有 $\%20$ 的数据不包含第二个操作，直接上小$M$的作物发现自己忘了，没办法只好自己瞎 $YY$ 一通。最后的结果发现是最小割，然后拆点，拆成牛羊两个点，源点连牛点，边权自然是其收益，羊点同理。然后中间连一条边权为 $inf$ 的边，表示这个要不圈牛要不圈羊只能圈一个。

嗯，发现还挺有道理的。对于，对于限制的话我们只需要再限制的两个牛羊点之间连上一条边权为 $inf$ 的边即可。

一遍过样例，美滋滋地开始造数据拍，嗯第一次和爆搜拍得挺顺利 $500$ 组数据全过了。

没过瘾，再来一组，结果第二组 $500$ 数据，拍到三百多个就 $WA$ 了……

后面没有想出来，于是弃疗了。

接下来讲一讲正解怎么做

小$M$的作物自然不用讲，我们来讲讲文理分科怎么做。

对于本题的第二个操作，我们需要新建一个结点 $p​$ ，然后如果这个操作的 $a​$ 是 $0​$ 我们就从源点向其连一条边权为 $b​$ 的边，$a​$ 是 $1​$ 的情况同理。

然后呢，对于 $S$ 中的每个点，如果 $a$ 为 $0$ 则从 $p$ 向该点连边，$a$ 是 $1$ 的情况同理。

嗯，然后就是不需要拆点。然后就差不多了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+2;
const int inf=1e9+9;

int n,m,k,a[N],b[N];
template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Dinic{
    queue<int> q;
    int s,t,head[N],dep[N],cnt=1;
    struct Edge{int nxt,to,val;}G[N<<1];
    inline void add(int u,int v,int w) {
        G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
        G[++cnt]=(Edge){head[v],u,0},head[v]=cnt;
    }
    int bfs() {
        memset(dep,0,sizeof(dep));
        dep[s]=1,q.push(s);
        while(!q.empty()) {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=G[i].nxt) {
                int v=G[i].to;
                if(!dep[v]&&G[i].val>0) 
                    dep[v]=dep[u]+1,q.push(v);
            }
        }return dep[t];
    }
    int dfs(int u,int flow) {
        if(u==t||!flow) return flow;
        int used=0,rlow;
        for(int i=head[u];i;i=G[i].nxt) {
            int v=G[i].to;
            if(dep[v]==dep[u]+1&&G[i].val>0) {
                used+=(rlow=dfs(v,min(flow-used,G[i].val)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        }if(!used) dep[u]=-1;
        return used;
    }
}using namespace Dinic;

int main() {
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
    IN(n),IN(m),IN(k);
    int sum=0,nodetot=n+1;s=0,t=n+1;
    for(int i=1;i<=n;++i) IN(a[i]),sum+=a[i];
    for(int i=1;i<=n;++i) IN(b[i]);
    for(int i=1;i<=m;++i) {
        int x,y,z;IN(x),IN(y),IN(z);
        add(x,y,z),add(y,x,z);
    }
    for(int i=1;i<=k;++i) {
        int size,x,y;
        IN(size),IN(x),IN(y);
        sum+=y,++nodetot;
        x?add(nodetot,t,y):add(s,nodetot,y);
        for(int j=1;j<=size;++j) {
            int c;IN(c);
            x?add(c,nodetot,inf):add(nodetot,c,inf);
        }
    }
    for(int i=1;i<=n;++i) {
        if(a[i]>=b[i]) add(s,i,a[i]-b[i]);
        else add(i,t,b[i]-a[i]),sum+=b[i]-a[i];
    }
    int maxflow=0;
    while(bfs()) maxflow+=dfs(s,inf);
    printf("%d\n",sum-maxflow);
    return 0;
}

本文标题:【考试总结】 Test-2019.4.3 HNOI2019模拟

文章作者:Qiuly

发布时间:2019年04月03日 - 00:00

最后更新:2019年04月03日 - 17:48

原始链接:http://qiulyblog.github.io/2019/04/03/[考试总结]test20190403/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。